package com.hc.programming.tree;

import java.util.Arrays;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * 有效 二叉搜索树定义如下：
 * * 节点的左子树只包含 小于 当前节点的数。
 * * 节点的右子树只包含 大于 当前节点的数。
 * * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 示例 1：
 * <a href="./找树左下角的值-示例1.png">示例1</a>
 * 输入：root = [2,1,3]
 * 输出：true
 * 示例 2：
 * <a href="./验证二叉搜索树-示例2.png">示例2</a>
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * <p>
 * 提示：
 * 树中节点数目范围在[1, 10^4] 内
 * -2^31 <= Node.val <= 2^31 - 1
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/16 10:49
 */
public class 验证二叉搜索树 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{2, 1, 3};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isValidBST(tree));
        arr = new Integer[]{5, 1, 4, null, null, 3, 6};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isValidBST(tree));
        arr = new Integer[]{5, 4, 6, null, null, 3, 7};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isValidBST(tree));
        arr = new Integer[]{3, 1, 5, 0, 2, 4, 6, null, null, null, 3};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isValidBST(tree));
        arr = new Integer[]{-2147483648, null, 2147483647};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isValidBST(tree));
    }

    public static boolean isValidBST(TreeNode root) {
        if (root == null) return false;
//        return 递归验证(root, null, null);
//        return 递归验证2(root, null, null);

        pre = null;
        return 递归验证3(root);
    }

    private static Integer pre = null;

    /**
     * 中序遍历，每次记录上一个值，判断是否大于等于当前值
     */
    private static boolean 递归验证3(TreeNode root) {
        if (root.left != null && !递归验证3(root.left)) return false;
        if (pre != null && pre >= root.val) {
            return false;
        }
        pre = root.val;
        return root.right == null || 递归验证3(root.right);
    }

    /**
     * 当前节点仅处理自己
     */
    private static boolean 递归验证2(TreeNode root, Integer minValue, Integer maxValue) {
        if (minValue != null && root.val <= minValue) return false;
        if (maxValue != null && root.val >= maxValue) return false;
        boolean left = root.left == null || 递归验证2(root.left, minValue, root.val);
        boolean right = root.right == null || 递归验证2(root.right, root.val, maxValue);
        return left && right;
    }

    /**
     * 当前节点判断子节点
     */
    private static boolean 递归验证(TreeNode root, Integer minValue, Integer maxValue) {
        if (root.left == null && root.right == null) return true;
        if (root.left != null && (root.left.val >= root.val || (minValue != null && root.left.val <= minValue) || !递归验证(root.left, minValue, root.val)))
            return false;
        if (root.right != null && (root.right.val <= root.val || (maxValue != null && root.right.val >= maxValue) || !递归验证(root.right, root.val, maxValue)))
            return false;
        return true;
    }
}
